package com.cdream.basic.algorithm.leetcode.array;

import java.util.Arrays;

/**
 * @author cdream
 * @date 8/4/21
 */
public class Question611 {
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int c = 0;
        for(int i = 0; i<n-2;i++){
            int k = i;
            for(int j = i+1;j<n-1;j++){
                while(k+1<n && nums[i]+nums[j]>nums[k+1]){
                    k++;
                }
                c += Math.max(k - j, 0); ;
            }
        }
        return c;
    }

    public static void main(String[] args) {
        new Question611().triangleNumber(new int[]{2,2,3,4});
    }
}
